package main

import (
	"fmt"
	"sort"
)

/*
四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。


示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 */

func fourSum(nums []int, target int) [][]int {
	res := make([][]int, 0)
	if len(nums) < 4 {
		return nil
	}

	sort.Ints(nums)
	// 固定两个数  双指针遍历
	for i := 0; i < len(nums) - 1; i ++ {
		for j := i + 1; j < len(nums); j ++ {
			// 排除值重复的固定位
			if i > 0 && nums[i] == nums[i-1] {
				continue
			}
			if j > 1 && nums[j] == nums[j-1] {
				continue
			}
			left, right := j + 1, len(nums) - 1
			if nums[i] + nums[j] > target {   // 前面两个数都大于目标值， 不用继续与后面的值相加了
				return res
			}

			for left < right {
				sum := nums[i] + nums[j] + nums[left] + nums[right]
				switch {
				case sum == target:
					res = append(res, []int{ nums[i], nums[j], nums[left], nums[right]})
					// 去重
					for left < right && nums[left] == nums[left] + 1 {
						left ++
					}
					for left < right && nums[right] == nums[right - 1] {
						right --
					}
					left ++
					right --
				case sum > target:
					// 右移指针
					right --
				case sum < target:
					// 左移指针
					left ++
				}
			}
		}
	}

	return res

}

func main() {
	fmt.Println(fourSum([]int{-2,-1,-1,1,1,2,2}, 0))
}
